{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #High Five"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: highFive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #前五科的均分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个不同学生的分数列表 <code>items</code>，其中 <code>items[i] = [ID<sub>i</sub>, score<sub>i</sub>]</code> 表示 <code>ID<sub>i</sub></code> 的学生的一科分数，你需要计算每个学生 <strong>最高的五科 </strong>成绩的 <strong>平均分</strong>。</p>\n",
    "\n",
    "<p>返回答案 <code>result</code> 以数对数组形式给出<em>，</em>其中<em> </em><code>result[j] = [ID<sub>j</sub>, topFiveAverage<sub>j</sub>]</code><em> </em>表示<em> </em><code>ID<sub>j</sub></code><em> </em>的学生和他 <strong>最高的五科 </strong>成绩的 <strong>平均分</strong><em>。</em><code>result</code><em> </em>需要按<em> </em><code>ID<sub>j</sub></code><em>  </em>递增的 <strong>顺序排列</strong> 。</p>\n",
    "\n",
    "<p>学生 <strong>最高的五科 </strong>成绩的 <strong>平均分 </strong>的计算方法是将最高的五科分数相加，然后用 <strong>整数除法</strong> 除以 5 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]\n",
    "<strong>输出：</strong>[[1,87],[2,88]]\n",
    "<strong>解释：</strong>\n",
    "ID = 1 的学生分数为 91、92、60、65、87 和 100 。前五科的平均分 (100 + 92 + 91 + 87 + 65) / 5 = 87\n",
    "ID = 2 的学生分数为 93、97、77、100 和 76 。前五科的平均分 (100 + 97 + 93 + 77 + 76) / 5 = 88.6，但是由于使用整数除法，结果转换为 88\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]\n",
    "<strong>输出：</strong>[[1,100],[7,100]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= items.length <= 1000</code></li>\n",
    "\t<li><code>items[i].length == 2</code></li>\n",
    "\t<li><code>1 <= ID<sub>i</sub> <= 1000</code></li>\n",
    "\t<li><code>0 <= score<sub>i</sub> <= 100</code></li>\n",
    "\t<li>对于每个 <code>ID<sub>i</sub></code>，<strong>至少</strong> 存在五个分数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [high-five](https://leetcode.cn/problems/high-five/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [high-five](https://leetcode.cn/problems/high-five/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]', '[[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        record = collections.defaultdict(list)\n",
    "        for item in items:\n",
    "            record[item[0]].append(item[1])\n",
    "        \n",
    "        res = []\n",
    "        for key in sorted(record.keys()):\n",
    "            heapq.heapify(record[key])\n",
    "            while len(record[key]) > 5:\n",
    "                heapq.heappop(record[key])\n",
    "            # print(key, record[key])\n",
    "            res.append([key, sum(record[key])//5])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda x:x[0])\n",
    "        dic = dict()\n",
    "        for x,y in items:\n",
    "            if x not in dic:\n",
    "                dic[x] = [y]\n",
    "            else:\n",
    "                dic[x] += [y]\n",
    "\n",
    "        res = list()\n",
    "        for k,v in dic.items():\n",
    "            v.sort(reverse=True)\n",
    "            res.append([k,sum(v[:5])//5])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda item:[-item[0], item[1]],reverse=True)\n",
    "        res = defaultdict(list)\n",
    "        for item in items:\n",
    "            student_id, score = item\n",
    "            if len(res[student_id]) < 5:\n",
    "                res[student_id].append(score)\n",
    "        return sorted([[student_id, sum(score) // 5] for student_id, score in res.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        dict = {}\n",
    "\n",
    "        for item in items:\n",
    "            if item[0] not in dict:\n",
    "                dict[item[0]] = []\n",
    "            heappush(dict[item[0]], item[1])\n",
    "            if len(dict[item[0]]) > 5:\n",
    "                heappop(dict[item[0]])\n",
    "        ans = []\n",
    "        for k, v in dict.items():\n",
    "            ans.append([k, sum(v) // 5])\n",
    "        ans.sort(key=lambda x: x[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        for item in items:\n",
    "            if item[0] in dic:\n",
    "                dic[item[0]].append(item[1])\n",
    "            else:\n",
    "                dic[item[0]] = [item[1]]\n",
    "        ans = []\n",
    "        for id, lst in dic.items():\n",
    "            heapq.heapify(lst)\n",
    "            ans.append([id, sum(heapq.nlargest(5, lst)) // 5])\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        student_score = collections.defaultdict(list)\n",
    "        for student, score in items:\n",
    "            if len(student_score[student]) < 5:\n",
    "                heapq.heappush(student_score[student], score)\n",
    "            else:\n",
    "                heapq.heappushpop(student_score[student], score)\n",
    "        return [[student, sum(scores) // 5] for student, scores in sorted(student_score.items(), key=lambda x: x[0])]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        dic = defaultdict(list)\n",
    "        for idx, score in items:\n",
    "            dic[idx].append(score)\n",
    "        \n",
    "        ans = []\n",
    "        for idx in sorted(dic):\n",
    "            dic[idx].sort(reverse = True)\n",
    "            ans .append([idx, sum(dic[idx][:5])//5])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        lib = {}\n",
    "        result=[]\n",
    "        for i in range(len(items)):\n",
    "            if items[i][0] not in lib:\n",
    "                lib[items[i][0]] = [items[i][1]]\n",
    "            else:\n",
    "                lib[items[i][0]].append(items[i][1])\n",
    "        for j in lib.keys():\n",
    "            scores = sorted(lib[j], reverse=True)\n",
    "            mean = sum(scores[:5])//5\n",
    "            result.append([j,mean])\n",
    "        return sorted(result,reverse=False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from heapq import *\n",
    "\"\"\"\n",
    "找出top 5的分数，用大小为5的max heap\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        if not items: return []\n",
    "\n",
    "        id_to_scores = defaultdict(list)\n",
    "        res = []\n",
    "\n",
    "        for sid, score in items:\n",
    "            heappush(id_to_scores[sid], score)\n",
    "\n",
    "            if len(id_to_scores[sid]) > 5:\n",
    "                heappop(id_to_scores[sid])\n",
    "                        \n",
    "        for sid, scores in id_to_scores.items():\n",
    "            res.append([sid, sum(scores) // 5])\n",
    "\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key = lambda x : [-x[0],x[1]], reverse = True)\n",
    "        res = collections.defaultdict(list)\n",
    "\n",
    "        for item in items:\n",
    "            idx, score = item\n",
    "            if len(res[idx]) < 5:\n",
    "                res[idx].append(score)\n",
    "        \n",
    "        return sorted([[student_id, sum(score) // 5] for student_id, score in res.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        from collections import defaultdict\n",
    "        from heapq import heappush, heappop\n",
    "        myMemo = defaultdict(list)\n",
    "        for item in items:\n",
    "            heappush(myMemo[item[0]], -item[1])\n",
    "        res = []\n",
    "        for id in myMemo:\n",
    "            idSum = 0\n",
    "            for i in range(5):\n",
    "                idSum -= heappop(myMemo[id])\n",
    "            res.append([id, idSum//5])\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from heapq import *\n",
    "\"\"\"\n",
    "找出top 5的分数，用大小为5的max heap\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        if not items: return []\n",
    "\n",
    "        id_to_scores = defaultdict(list)\n",
    "        res = []\n",
    "\n",
    "        for sid, score in items:\n",
    "            heappush(id_to_scores[sid], score)\n",
    "\n",
    "            if len(id_to_scores[sid]) > 5:\n",
    "                heappop(id_to_scores[sid])\n",
    "                        \n",
    "        for sid, scores in id_to_scores.items():\n",
    "            res.append([sid, sum(scores) // 5])\n",
    "\n",
    "        return sorted(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        tmpDict = defaultdict(list)\n",
    "        for item in items:\n",
    "            if len(tmpDict[item[0]]) < 5:\n",
    "                heapq.heappush(tmpDict[item[0]], item[1])\n",
    "            else:\n",
    "                heapq.heappushpop(tmpDict[item[0]], item[1])\n",
    "\n",
    "        res = []\n",
    "        for student, scores in tmpDict.items():\n",
    "            res.append([student, sum(scores) // len(scores)])\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        dict = {}\n",
    "\n",
    "        for item in items:\n",
    "            if item[0] not in dict:\n",
    "                dict[item[0]] = []\n",
    "            heappush(dict[item[0]], item[1])\n",
    "            if len(dict[item[0]]) > 5:\n",
    "                heappop(dict[item[0]])\n",
    "        ans = []\n",
    "        for k, v in dict.items():\n",
    "            ans.append([k, sum(v) // 5])\n",
    "        ans.sort(key=lambda x: x[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        queue = {}\n",
    "        for k, v in items:\n",
    "            if queue.get(k, 0) == 0:\n",
    "                queue[k] = []\n",
    "            heapq.heappush(queue[k], -v)\n",
    "        res = []\n",
    "        for x, y in queue.items():\n",
    "            tmp = 0\n",
    "            for _ in range(5):\n",
    "                tmp += -1 * heapq.heappop(y)\n",
    "            res.append([x, tmp // 5])\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        gradedict = {}\n",
    "\n",
    "        for i, score in items:\n",
    "            if i not in gradedict:\n",
    "                gradedict[i] = [score]\n",
    "            else:\n",
    "                heapq.heappush(gradedict[i], score)\n",
    "                if len(gradedict[i]) > 5:\n",
    "                    heapq.heappop(gradedict[i])\n",
    "        \n",
    "        ans = []\n",
    "        for i, scores in gradedict.items():\n",
    "            avg = sum(scores) // len(scores)\n",
    "            ans.append([i, avg])\n",
    "        \n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        students = collections.defaultdict(list)\n",
    "        for item in items:\n",
    "            students[item[0]].append(-item[1])\n",
    "        students = sorted(students.items(), key=lambda x: x[0])\n",
    "        output = []\n",
    "        for d in students:\n",
    "            sid = d[0]\n",
    "            scores = d[1]\n",
    "            heapq.heapify(scores)\n",
    "            score = 0\n",
    "            for i in range(5):\n",
    "                score += - heapq.heappop(scores)\n",
    "            score = score // 5\n",
    "            output.append([sid, score])\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        m = defaultdict(list)\n",
    "        for item in items:\n",
    "            arr = m[item[0]]\n",
    "            heappush(arr, item[1])\n",
    "            if len(arr) > 5:\n",
    "                heappop(arr)\n",
    "            m[item[0]] = arr\n",
    "\n",
    "        res = []\n",
    "        for k in m.keys():\n",
    "            res.append([k, sum(m[k]) // 5])\n",
    "        res = sorted(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        scores = collections.defaultdict(list)\n",
    "\n",
    "        for ID, score in items:\n",
    "            heapq.heappush(scores[ID], score)\n",
    "\n",
    "        ret = []\n",
    "        for ID in sorted(scores.keys()):\n",
    "            ret.append([ID, sum(heapq.nlargest(5, scores[ID])) // 5])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        dict = {}\n",
    "\n",
    "        for item in items:\n",
    "            if item[0] not in dict:\n",
    "                dict[item[0]] = []\n",
    "            heappush(dict[item[0]], item[1])\n",
    "            if len(dict[item[0]]) > 5:\n",
    "                heappop(dict[item[0]])\n",
    "        ans = []\n",
    "        for k, v in dict.items():\n",
    "            ans.append([k, sum(v) // 5])\n",
    "        ans.sort(key=lambda x: x[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        \n",
    "        items.sort(key=lambda x: x[0])\n",
    "        \n",
    "        pos = 0\n",
    "        while pos < len(items):\n",
    "            heap = []\n",
    "\n",
    "            curr = items[pos][0]\n",
    "            while pos < len(items) and items[pos][0] == curr:\n",
    "                if len(heap) < 5:\n",
    "                    heapq.heappush(heap, items[pos][1])\n",
    "                else:\n",
    "                    if items[pos][1] > heap[0]:\n",
    "                        heapq.heappop(heap)\n",
    "                        heapq.heappush(heap, items[pos][1])\n",
    "                pos += 1\n",
    "            \n",
    "            ans.append([curr, sum(heap) // 5])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        return self.answer_1(items)\n",
    "\n",
    "    def answer_1(self, items):\n",
    "        storage = defaultdict(list)\n",
    "\n",
    "        for idx, score in items:\n",
    "            q = storage[idx]\n",
    "            if len(q) > 5:\n",
    "                heapq.heappop(q)\n",
    "            heapq.heappush(q, score)\n",
    "\n",
    "        keys = sorted(storage.keys())\n",
    "\n",
    "        result = []\n",
    "        for key in keys:\n",
    "            q = storage[key]\n",
    "            if len(q) > 5:\n",
    "                heapq.heappop(q)\n",
    "            result.append([key, sum(storage[key]) // len(storage[key])])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Python3 字典排序模拟\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda x:x[0])\n",
    "        dic = dict()\n",
    "        for x,y in items:\n",
    "            if x not in dic:\n",
    "                dic[x] = [y]\n",
    "            else:\n",
    "                dic[x] += [y]\n",
    "        res = list()\n",
    "        for k,v in dic.items():\n",
    "            v.sort(reverse=True)\n",
    "            res.append([k,sum(v[:5])//5])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "    \n",
    "        items = sorted(items, key = lambda x: (x[0], -x[1]))\n",
    "        i, res, n = 0, [], len(items)\n",
    "\n",
    "        while i < n:\n",
    "            cnt, csum = 0, 0\n",
    "            while i < n and cnt <= 4:\n",
    "                csum += items[i][1]\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "\n",
    "            if i <= n:\n",
    "                res.append([items[i - 1][0], csum // 5])\n",
    " \n",
    "            while i < n and items[i][0] == res[-1][0]:\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        for item in items:\n",
    "            if item[0] in dic:\n",
    "                dic[item[0]].append(item[1])\n",
    "            else:\n",
    "                dic[item[0]] = [item[1]]\n",
    "        ans = []\n",
    "        for id, lst in dic.items():\n",
    "            bheap = bigHeap(lst)\n",
    "            ans.append([id, sum(bheap.popN(5)) // 5])\n",
    "        ans.sort()\n",
    "        return ans\n",
    "\n",
    "class bigHeap:\n",
    "    def __init__(self, lst):\n",
    "        self.heap = [-i for i in lst]\n",
    "        heapq.heapify(self.heap)\n",
    "    \n",
    "    def popN(self, n):\n",
    "        return [-heapq.heappop(self.heap) for i in range(n)]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda items: [-items[0], items[1]], reverse=True)\n",
    "        student_dict = defaultdict(list)\n",
    "        for item in items:\n",
    "            k, v = item\n",
    "            if len(student_dict[k]) < 5:\n",
    "                student_dict[k].append(v)\n",
    "        return [[k, sum(v) // 5] for k, v in student_dict.items()]            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "\n",
    "        items.sort(key=lambda x: x[0])\n",
    "\n",
    "        pos = 0\n",
    "        while pos < len(items):\n",
    "            heap = []\n",
    "\n",
    "            cur = items[pos][0]\n",
    "            while pos < len(items) and items[pos][0] == cur:\n",
    "                if len(heap) < 5:\n",
    "                    heapq.heappush(heap, items[pos][1])\n",
    "                else:\n",
    "                    if heap[0] < items[pos][1]:\n",
    "                        heapq.heappop(heap)\n",
    "                        heapq.heappush(heap, items[pos][1])\n",
    "                pos += 1\n",
    "            \n",
    "            ans.append([cur, sum(heap) // 5])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda items:[-items[0],items[1]],reverse=True)\n",
    "        dic={}\n",
    "        res=[]\n",
    "        for item in items:\n",
    "            if item[0] in dic:\n",
    "                if dic[item[0]]<5:\n",
    "                    dic[item[0]]+=1\n",
    "                    res[-1][1]+=item[1]\n",
    "            else:\n",
    "                dic[item[0]]= dic.get(item[0], 0) + 1\n",
    "                res.append(item)\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i][1]=res[i][1]//5\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        d = defaultdict(list)\n",
    "        items.sort(key = lambda x:x[0])\n",
    "        for i,score in items:\n",
    "            heapq.heappush(d[i],-1*score)\n",
    "        res = []\n",
    "        for key in d.keys():\n",
    "            tmp = 0\n",
    "            for i in range(5):\n",
    "                tmp-=heapq.heappop(d[key])\n",
    "            res.append([key,tmp//5])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        scores = dict()\n",
    "        for item in items:\n",
    "            s = scores.get(item[0], [])\n",
    "            s.append(item[1])\n",
    "            scores[item[0]] = s\n",
    "        \n",
    "        result = []\n",
    "        for i in scores.keys():\n",
    "            score = scores[i]\n",
    "            score.sort(reverse=True)\n",
    "            sum = 0\n",
    "            for j in range(0, 5):\n",
    "                sum += score[j]\n",
    "            result.append([i, math.floor(sum/5)])\n",
    "        \n",
    "        result.sort()\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        dict = defaultdict(list)\n",
    "        for idx, score in items:\n",
    "            dict[idx].append(score)\n",
    "        for k, v in dict.items():\n",
    "            v.sort(reverse=True)\n",
    "            res.append([k, sum(v[:5]) // 5])\n",
    "        return sorted(res, key=lambda x: x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda item: [-item[0], item[1]], reverse=True)\n",
    "        res = defaultdict(list)\n",
    "        for item in items:\n",
    "            student_id, score = item \n",
    "            if len(res[student_id]) < 5:\n",
    "                res[student_id].append(score)\n",
    "        return sorted([[student_id, sum(score) // 5] for student_id, score in res.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key = lambda x : (x[0], -x[1]))\n",
    "        result = []\n",
    "        if len(items) <= 5:\n",
    "            return [[items[0][0], sum([items[i][1] for i in range(len(items))]) // len(items)]]\n",
    "        i = 0\n",
    "\n",
    "        while i < len(items):\n",
    "            id = items[i][0]\n",
    "            j = 0\n",
    "            sum_top5 = 0\n",
    "            while i + j < len(items) and j < 5:\n",
    "                sum_top5 += items[i + j][1]\n",
    "                j += 1\n",
    "            result.append([items[i][0], sum_top5 // j])\n",
    "            i += j\n",
    "            while i < len(items) and items[i][0] == id:\n",
    "                i += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        scores=defaultdict(list)\n",
    "        for student,score in items:\n",
    "\n",
    "            heapq.heappush(scores[student-1],score)\n",
    "            if len(scores[student-1])==6:\n",
    "                heapq.heappop(scores[student-1])\n",
    "        ans=[]\n",
    "        for student in sorted(scores.keys()):\n",
    "            ans.append([student+1,sum(scores[student])//5])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        scores = collections.defaultdict(list)\n",
    "        for ID, score in items:\n",
    "            heapq.heappush(scores[ID], score)\n",
    "\n",
    "        return [[ID, sum(heapq.nlargest(5, scores[ID])) // 5] for ID in sorted(scores.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        # efaultdict() defaultdict是属于collections 模块下的一个工厂函数，\n",
    "        # 用于构建字典对象，接收一个函数（可调用）对象为作为参数。\n",
    "        # 参数返回的类型是什么，key对应value就是什么类型\n",
    "        items.sort(key=lambda x:[x[0],-x[1]])\n",
    "        print(items)\n",
    "        scores=defaultdict(list)\n",
    "\n",
    "        for person, grade in items:\n",
    "            scores[person].append(grade)\n",
    "        res=[]\n",
    "        for key,value in scores.items():\n",
    "            avg=sum(value[:5])//5\n",
    "            res.append([key,avg])\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        student_nums = defaultdict(list)\n",
    "        for student, num in items:\n",
    "            student_nums[student].append(num)\n",
    "        \n",
    "        res = []\n",
    "        for stu, nums in student_nums.items():\n",
    "            nums.sort()\n",
    "            aver = sum(nums[-5: ]) // 5\n",
    "            res.append([stu, aver])\n",
    "        res.sort(key = lambda x: x[0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "        score_map = defaultdict(list)\n",
    "\n",
    "        for ID, score in items:\n",
    "            score_map[ID].append(score)\n",
    "        \n",
    "        for ID, score in score_map.items():\n",
    "            top_five_avg = sum(sorted(score, reverse=True)[:5]) // 5\n",
    "            result.append([ID, top_five_avg])\n",
    "        \n",
    "        result.sort(key= lambda x : x[0])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "    \n",
    "        items = sorted(items, key = lambda x: (x[0], -x[1]))\n",
    "        i, res, n = 0, [], len(items)\n",
    "        print(items)\n",
    "\n",
    "\n",
    "        while i < n:\n",
    "            cnt, csum = 0, 0\n",
    "            while i < n and cnt <= 4:\n",
    "                csum += items[i][1]\n",
    "                # print(items[i][1])\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "\n",
    "            if i <= n:\n",
    "                res.append([items[i - 1][0], csum // 5])\n",
    " \n",
    "            while i < n and items[i][0] == res[-1][0]:\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda x:x[0])#按照学生id排序\n",
    "        dic = dict()#字典，记录学生x的各科分数\n",
    "        for x,y in items:\n",
    "            if x not in dic:\n",
    "                dic[x] = [y]\n",
    "            else:\n",
    "                dic[x] += [y]\n",
    "        res = list()\n",
    "        for k,v in dic.items():\n",
    "            v.sort(reverse=True)\n",
    "            res.append([k,sum(v[:5])//5])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        dict = defaultdict(list)\n",
    "        for idx, score in items:\n",
    "            dict[idx].append(score)\n",
    "        for k, v in dict.items():\n",
    "            v.sort(reverse=True)\n",
    "            res.append([k, sum(v[:5]) // 5])\n",
    "        return sorted(res, key=lambda x: x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda item:[-item[0], item[1]], reverse=True)\n",
    "        res = defaultdict(list)\n",
    "        for item in items:\n",
    "            stid, score = item\n",
    "            if len(res[stid])<5:\n",
    "                res[stid].append(score)\n",
    "        return [[stid, sum(score)//5] for stid, score in res.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda item:[-item[0], item[1]],reverse=True)\n",
    "        res = defaultdict(list)\n",
    "        for item in items:\n",
    "            student_id, score = item\n",
    "            if len(res[student_id]) < 5:\n",
    "                res[student_id].append(score)\n",
    "        return sorted([[student_id, sum(score) // 5] for student_id, score in res.items()])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "    \n",
    "        items = sorted(items, key = lambda x: (x[0], -x[1]))\n",
    "        i, res, n = 0, [], len(items)\n",
    "        print(items)\n",
    "\n",
    "\n",
    "        while i < n:\n",
    "            cnt, csum = 0, 0\n",
    "            while i < n and cnt <= 4:\n",
    "                csum += items[i][1]\n",
    "                # print(items[i][1])\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "\n",
    "            if i <= n:\n",
    "                res.append([items[i - 1][0], csum // 5])\n",
    " \n",
    "            while i < n and items[i][0] == res[-1][0]:\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import insort_left\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        memory = defaultdict(list)\n",
    "        \n",
    "        for pid, score in items:\n",
    "            his_scores = memory[pid]\n",
    "            if not his_scores:\n",
    "                his_scores.append(score)\n",
    "            else:\n",
    "                idx = 0\n",
    "                for i, s in enumerate(his_scores):\n",
    "                    if score >= s:\n",
    "                        idx = i + 1\n",
    "                if idx == len(his_scores):\n",
    "                    memory[pid].append(score)\n",
    "                else:\n",
    "                    memory[pid] = memory[pid][:idx] + [score] + memory[pid][idx:]\n",
    "                memory[pid] = memory[pid][-5:]\n",
    "        ret = []\n",
    "        for pid in memory:\n",
    "            \n",
    "            ret.append([pid, sum(memory[pid])//len(memory[pid])])\n",
    "        return sorted(ret, key=lambda x: x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda item:[-item[0], item[1]],reverse=True)\n",
    "        res = defaultdict(list)\n",
    "        for item in items:\n",
    "            student_id, score = item\n",
    "            if len(res[student_id]) < 5:\n",
    "                res[student_id].append(score)\n",
    "        return sorted([[student_id, sum(score) // 5] for student_id, score in res.items()])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        scoreboard = defaultdict(list)\n",
    "        for i in items:\n",
    "            heapq.heappush(scoreboard[i[0]],i[1])\n",
    "            if len(scoreboard[i[0]])>5:\n",
    "                heapq.heappop(scoreboard[i[0]])\n",
    "        res = []\n",
    "        for id,scores in scoreboard.items():\n",
    "            res.append([id,int(sum(scores)/len(scores))])\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        maxHeap = []\n",
    "        for s_id, score in items:\n",
    "            heapq.heappush(maxHeap, (-score, s_id))\n",
    "        store = collections.defaultdict(list)\n",
    "        while maxHeap:\n",
    "            score, s_id = heapq.heappop(maxHeap)\n",
    "            if s_id in store and len(store[s_id]) == 5:\n",
    "                continue\n",
    "            store[s_id].append(-score)\n",
    "        return sorted([[s_id, sum(score_list) // 5] for s_id, score_list in store.items()], key=lambda x: x[0]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        from queue import PriorityQueue\n",
    "\n",
    "        id_queue_dict = {}\n",
    "\n",
    "        for uid, score in items:\n",
    "            q = id_queue_dict.get(uid, PriorityQueue())\n",
    "            q.put(-score)\n",
    "            id_queue_dict[uid] = q\n",
    "        \n",
    "        ans = []\n",
    "        for uid, q in id_queue_dict.items():\n",
    "            \n",
    "            sums = 0\n",
    "            for i in range(5):\n",
    "                sums += q.get()\n",
    "            ans.append([uid, -sums//5])\n",
    "        \n",
    "        return sorted(ans, key=lambda x: x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key = lambda p:(p[0], -p[1]))\n",
    "        res = []\n",
    "        cnt = Counter()\n",
    "        s = 0\n",
    "        for i, x in items:\n",
    "            if cnt[i] == 5: continue\n",
    "            cnt[i] += 1\n",
    "            s += x \n",
    "            if cnt[i] == 5:\n",
    "                res.append([i, s // 5])\n",
    "                s = 0\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda item:[-item[0], item[1]],reverse=True)\n",
    "        res = defaultdict(list)\n",
    "        for item in items:\n",
    "            student_id, score = item\n",
    "            if len(res[student_id]) < 5:\n",
    "                res[student_id].append(score)\n",
    "        return sorted([[student_id, sum(score) // 5] for student_id, score in res.items()])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda items: [-items[0], items[1]], reverse=True)\n",
    "        student_dict = defaultdict(list)\n",
    "        for item in items:\n",
    "            k, v = item\n",
    "            if len(student_dict[k]) < 5:\n",
    "                student_dict[k].append(v)\n",
    "        return [[k, sum(v) // 5] for k, v in student_dict.items()]            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items.sort(key=lambda x:[x[0],-x[1]])\n",
    "        print(items)\n",
    "        scores=defaultdict(list)\n",
    "\n",
    "        for person, grade in items:\n",
    "            scores[person].append(grade)\n",
    "        res=[]\n",
    "        for key,value in scores.items():\n",
    "            avg=sum(value[:5])//5\n",
    "            res.append([key,avg])\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "    \n",
    "        items = sorted(items, key = lambda x: (x[0], -x[1]))\n",
    "        i, res, n = 0, [], len(items)\n",
    "\n",
    "        while i < n:\n",
    "            cnt, csum = 0, 0\n",
    "            while i < n and cnt <= 4:\n",
    "                csum += items[i][1]\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "\n",
    "            if i <= n:\n",
    "                res.append([items[i - 1][0], csum // 5])\n",
    " \n",
    "            while i < n and items[i][0] == res[-1][0]:\n",
    "                i += 1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
